package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_131 {

    private List<List<String>> rst;

    public List<List<String>> partition(String s) {
        rst = new ArrayList<>();
        dps(s.toCharArray(), 0, new ArrayList<>());
        return rst;
    }

    private boolean isPartition(char[] chars, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            if (chars[i] != chars[j]) {
                return false;
            }
        }
        return true;
    }

    private void dps(char[] chars, int begin, List<String> list) {
        if (begin == chars.length) {
            rst.add(new ArrayList<>(list));
        } else {
            for (int i = begin; i < chars.length; i++) {
                if (isPartition(chars, begin, i)) {
                    String str = new String(chars, begin, i - begin + 1);
                    list.add(str);
                    dps(chars, i + 1, list);
                    list.remove(list.size() - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution_131 model = new Solution_131();
        System.out.println(model.partition("aab"));
        System.out.println(model.partition("a"));
    }
}
